package org.laizili.solution.nowcodertop101.list;

import org.laizili.structure.list.ListNode;

/**
 * <a href="https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&sfm=html&channel=nowcoder">BM2 链表内指定区间反转</a>
 * <p>
 * tags: 链表; 头插法;
 * notes: 用一个头结点简化插入操作
 */
public class BM2 {
    private static class Solution {
        /**
         * @param head ListNode类
         * @param m    int整型
         * @param n    int整型
         * @return ListNode类
         */
        public ListNode reverseBetween(ListNode head, int m, int n) {
            // write code here
            // 哑结点
            ListNode dummy = new ListNode();
            dummy.next = head;
            ListNode prev = dummy;
            ListNode cur = head;
            for (int i = 1; i < m; i++) {
                prev = cur;
                cur = cur.next;
            }
            for (int i = m; i < n; i++) {
                ListNode tmp = cur.next;
                cur.next = tmp.next;
                tmp.next = prev.next;
                prev.next = tmp;
            }
            return dummy.next;
        }
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        ListNode cur = new Solution().reverseBetween(node1, 1, 3);
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }
}
